var search = function (nums, target) {
  if (nums.length == 0 || nums == null) return false;
  let low = 0;
  let high = nums.length - 1;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (nums[low] == target) return true;
    if (nums[mid] == target) return true;
    if (nums[high] == target) return true;

    if (nums[low] == nums[mid]) {
      // 1 0 1 1 1
      // 1 1 1 0 1
      low++;
      continue;
    }

    if (nums[low] < nums[mid]) {
      // 2 3 4 5 6 7 1
      if (nums[mid] > target && nums[low] <= target) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    } else {
      // 6 7 1 2 3 4 5
      if (nums[mid] < target && nums[high] >= target) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
  }
  return false;
};
